package com.xcc.datastructure;

/**
 * @Description 求【两个正序数组的中位数】练习
 *
 * 题目描述：
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 示例 2：
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 * <p>
 * 提示：
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -10的6次方 <= nums1[i], nums2[i] <= 10的6次方
 *
 * @Author xiechuang
 * @Date 2022/11/22
 */
public class FindMedianSortedArraysDemo {

    public static void main(String[] args) {

        int[] nums1 = { 1, 3 };
        int[] nums2 = { 2 };
        // 预期结果：2
        System.out.println(findMedianSortedArrays(nums1, nums2));

        int[] nums3 = {1, 2};
        int[] nums4 = {3, 4};
        // 预期结果：2.5
        System.out.println(findMedianSortedArrays(nums3, nums4));

    }

    /**
     * 思路：判断两个正序数组的长度和，为奇数则取合并后排序的中间值，为偶数则取中间两数平均值
     * 循环遍历：找到中间值之后跳出循环。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        // true为奇数，取中间值，false为偶数，取中间两个值的平均值
        boolean flag = (m + n) % 2 > 0;
        // 索引，用于下标移动
        int mi = 0;
        int ni = 0;
        double k1 = 0.0;

        int size = (m + n) / 2;
        double num = 0.0;

        for (int i = 0; i < m + n; i++) {
            if (mi == m) {
                num = nums2[ni];
                ni++;
            } else if (ni == n) {
                num = nums1[mi];
                mi++;
            } else if (nums1[mi] > nums2[ni]) {
                num = nums2[ni];
                ni++;
            } else {
                num = nums1[mi];
                mi++;
            }

            if ((i == size - 1) && !flag) {
                k1 = num;
            }

            if (i == size) {
                if (flag) {
                    k1 = num;
                } else {
                    k1 = (k1 + num) / 2;
                }
                break;
            }
        }
        return k1;
    }

}
